In early data communications networks, data flow control and error detection/recovery were typically performed at each intermediate node or system on the path between the source and destination systems. The hop-by-hop operations were believed to be needed to deal with data lost or corrupted as result of using the then-available high error rate data transmission technology and media.
Data transmission technology and media have improved over time, allowing data communications networks to evolve into systems in which flow control and error detection/recovery can become primarily the responsibility of nodes at the end points of a network data path. An effort is being made to minimize packet processing operations (and the time required to perform such operations) at intermediate nodes to reduce the time required to move the data from source to destination; that is, to increase system throughput.
Asynchronous Transfer Mode or ATM technology is an increasingly pervasive example of technology in which flow control and error detection/recovery are typically performed only at end nodes on a data path. In ATM systems, all data is transported in relatively short fixed length cells. Standard ATM cells have a five byte header, which carries cell control and routing information, and a forty-eight byte payload, which normally carries actual user data. The advantage of using fixed length cells is that such cells can be switched at extremely high speeds by special purpose hardware switches within the ATM network.
While the ATM cell structure may be standard, the data transported in such cells may represent divergent types of information, which have divergent, sometimes inconsistent characteristics and transport requirements. Transported data may represent computer data or audio information or image information. Examples of audio information include human speech or music. Examples of image information include "live" video or photographs or graphic or medical images.
Where the data being transported represents audio or video information, a loss of a certain amount of the data during transmission generally can be tolerated before the quality of the reconstructed audio or video information is noticeably degraded. However, certain kinds of such data, such as live video signals or speech, cannot be excessively delayed or subject to cell-to-cell end-to-end variations in transit time (that is, be subject to jitter) without causing a significant loss of quality of the reconstructed audio or video information. In contrast, a certain level of transmission delay or jitter is tolerable for computer data while loss or corruption of such data is generally intolerable.
Data which must be delivered with low tolerances on delay or jitter is characterized as real-time (RT) data. Data which is delay-tolerant is characterized as non-real-time (NRT) data. In most, but not necessarily all, cases, RT data is loss-tolerant while NRT data is loss-intolerant.
Any data communications network, including an ATM network, has a limited capacity (bandwidth) available for the transport of user data. The goal of a network designer or administrator is to consistently use as much of that bandwidth as possible while continuing to satisfy loss and/or delay requirements for the different kinds of data that are transported. Generically, loss and delay requirements are referred to as Quality of Service or QOS requirements.
In an ATM network, a connection is normally set up each time a source node wishes to send data to a destination node in the network. The connection setup includes the selection of a route or path through the network and the establishment of service parameters and QOS guarantees for the duration of the connection. Multiple connections between different source-destination pairs can concurrently use the same physical link in the network. To accommodate the different service requirements of different kinds of traffic in an ATM network, different classes of ATM traffic have been defined. The defined classes of interest here are CBR (Constant Bit Rate), VBR (Variable Bit Rate) and ABR (Available Bit Rate).
CBR traffic is traffic that needs to be transmitted at a specified, substantially constant bit rate. Examples of CBR traffic include real-time audio or video traffic or an ATM network connection emulating a standard T1 (1.544-Mbit/s) line. CBR traffic is delay and jitter intolerant. During set up of a CBR, a Peak Cell Rate (PCR) must be negotiated to define the maximum rate at which data can be transported without creating a significant risk of cell loss. Data is typically then transmitted at the negotiated PCR rate. If an attempt in made to transmit traffic at a rate exceeding the PCR, the excess traffic may be discarded by the network.
VBR traffic includes two subclasses of traffic--VBR real-time (VBR-RT) and VBR non-real-time (VBR-NRT). VBR-RT traffic is traffic which may be generated at varying rates (that is, be bursty) while still requiring tight limits on acceptable limits of cell jitter. Examples of VBR-RT traffic include video signals generated by a variable-rate codec or aggregated voice traffic with silence removal. VBR-NRT traffic is traffic which may be bursty but which is more delay tolerant than VBR-RT traffic. An example of VBR-NRT traffic includes traffic resulting from transaction processing, such as credit verification or other point-of-sale operations.
For each VBR connection to be set up, a Peak Cell Rate, a Sustained Cell Rate (SCR) and a jitter tolerance value must be negotiated. The negotiated SCR represents the average throughput to be permitted over the connection. While traffic may be accepted from a VBR source at rates exceeding the negotiated SCR for short periods of time (as long as the excess rates don't exceed the negotiated PCR), the rate at which traffic will subsequently be accepted from the same source must be reduced below the SCR sufficiently to maintain the negotiated SCR over a longer period of time. To assure that the SCR parameter can be observed over a relatively long period of time, still another parameter, a burst tolerance, must be established when the connection is being set-up. Burst tolerance defines how long a VBR connection will be allowed to accept traffic at rates greater than SCR before the traffic rate is reduced below SCR to maintain an overall throughput not exceeding SCR.
During these periods of reduced traffic activity and perhaps at other times during network operation, a significant amount of network bandwidth may be unused or idle. The ABR traffic class has been defined in an effort to exploit the availability of idle network bandwidth. ABR traffic is intended to make optimum use of what might otherwise be unused network bandwidth while utilizing traffic management techniques to monitor actual or incipient network congestion which might, if not taken into account, lead to unacceptable cell loss during transmission attempts.
The setup of an ABR connection requires negotiation of the same kind of PCR parameter that exists for a VBR connection. The PCR parameter serves the same purpose for both kinds of connections; namely, to limit the maximum rate at which traffic will be accepted for transmission over the connection. No effort is made to negotiate jitter or burst tolerances for ABR traffic. Instead, the ABR source and the network negotiate a Minimum Cell Rate (MCR) parameter representing the minimum amount of connection bandwidth that will always be available to the ABR traffic source. Generally, the MCR parameter represents the minimum transmission rate which must be available if the ABR traffic source or application is stay alive; i.e., continue to execute.
For CBR and VBR connections in an ATM network, no effort is made to dynamically control congestion (network traffic loads) from within the network. If, however, the goal is to utilize idle network bandwidth, it makes sense to attempt to dynamically control congestion through the use of a closed-loop congestion management techniques. Such techniques monitor network traffic and provide feedback to a traffic source to permit that source to adjust the rate at which traffic is made available to the network to levels which assure that existing QOS requirements continue to be observed.
A simple type of end-to-end control loop uses Explicit Forward Congestion Indicator (EFCI) messages generated by intermediate switches on a data path. An intermediate switch capable of supporting EFCI operation can set an EFCI indicator in the header of an in-transit regular data cell to indicate that the network is congested at the intermediate switch. When the cell reaches the connection destination, the destination node stores the congestion information until it receives a special Resource Management (RM) cell from the source node. The destination node writes the congestion information into the RM cell and returns that cell to the source node.
Some intermediate switches don't explicitly support EFCI operation but can write congestion information into Congestion Indicator (CI) and No.sub.-- increase Indicator (NI) bits in a regular data cell header. The CI/NI information is forwarded to the destination node and stored there until a RM cell can be returned to the source node.
For either EFCI or CI/NI operation, the source node responds to a congestion notification in an RM cell by reducing its transmission rate. In either an EFCI or a CI/NI control loop, the intermediate switches play a very limited role, providing only a binary indication (congested or not congested) rather than a quantitative indication of the degree of congestion or the level of available bandwidth. Therefore, there is no assurance that the response of the source node will be appropriate for the actual congestion conditions in the network.
A more sophisticated feedback mechanism, identified as Explicit Rate Marking (ERM), allows the intermediate switches to play a larger role in the control of network congestion. Generally speaking, a switch implementing ERM feedback can provide quantitative information about the amount of bandwidth available at a given time at the switch. When such information is made available to the source station through the use of RM cells, the source station can respond by adjusting the transmission rate to a level which results in improved utilization of the idle bandwidth.
Different algorithms or methods can be used to generate ER values. One proposal, R. Jain, "A Sample Switch Algorithm," ATM.sub.-- Forum/95-0178R1, February 1995, is for each intermediate switch on a path to monitor the load on each outgoing link to determine the overload factor and the number of active ABR connections on that link. The overload factor for a link is a function of the input rate N/T and the target cell rate U.sup.* C where N is the number of cells received during a time period T, U.sup.* is the target link utilization factor and C is the capacity or bandwidth of the link. The target link utilization factor U.sup.* is always less than 100%, and is preferably is on the order of 80%-90%, reflecting the reality that 100% of a link's theoretical capacity is not going available for use in a real network.
The overload factor is defined as the ratio of the input rate over the target cell rate; that is, N/(TU.sup.* C). Under this approach, an Er.sub.i value for ABR connection i is: ##EQU1## where n is the number of active ABR connections and CCR is the current cell rate, the rate at which cells are currently being transmitted over the connection.
One disadvantage of the above algorithm is that it ignores ABR buffer capacity, which might be available at any given time.
Another proposal is set forth in A. Barnhart, "Explicit Rate Performance Evaluation," ATM.sub.-- Forum/94-0983, October 1994. According that proposal, each intermediate switch on a data path makes measurements which permit it to determine the actual input rate and the target output rate for an ABR connection. A connection-explicit ER value is established as a function of the ratio of the actual input rate to the target output rate. Connections which have an actual input rate less than the target output rate are allowed to increase their transmission rate. Conversely, connections which have an actual input rate exceeding their target output rate are required to reduce their transmission rate.
The proposal does not define how current available bandwidth is determined or how the target output rate for an ABR connection is derived. Both of these are described in the technical description of the present invention.